﻿// 7-10 完全二叉搜索树 (30分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
user:Lidongcheng
date:20191217 2 days
level:9
key:1.我们是对每一个节点做操作，所以对左右孩子的操作之前一定要先检查他们是否为空。
2.完全二叉树就是从左至右填满它，按层序遍历建树即可，这里分为总数为偶数与奇数两种情况，如果是偶数我们两个两个放没有问题，如果是奇数计数器最后会与n相距1，
这种情况我们只填左子树就好了。
3.搜索树就是按中序遍历输出是有序，那么反过来想就是将原本就有序的数按中序遍历输出。
*/

#include <iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
class tree
{
public:
	int flag;
	int inf;
	tree* l;
	tree* r;
	tree()
	{
		l = NULL;
		r = NULL;
		inf = -1;
		flag = 0;

	}
	void creat()
	{
		l = new tree();
		r = new tree();
	}
	void creatl()
	{
		l = new tree();

	}
};

void op(tree* p)
	{
		int u;
		int c[3];
		if (p->l != NULL && p->r == NULL) {
			if (p->l->inf > p->inf) {
				u = p->l->inf;
				p->l->inf = p->inf;
				p->inf = u;
			}
		}
		if (p->l == NULL && p->r != NULL) {
			if (p->r->inf < p->inf) {
				u = p->r->inf;
				p->r->inf = p->inf;
				p->inf = u;
			}

		}
		if (p->l != NULL && p->r != NULL)
		{
			c[0] = p->l->inf;
			c[1] = p->r->inf;
			c[2] = p->inf;
			sort(c, c + 3);
			p->l->inf = c[0];
			p->inf = c[1];
			p->r->inf = c[2];
		}
		else
		{
			
		}
	}


void write_mid_line(tree* p, queue<int>& c)
{
	
	if (p->inf!=-1)
	{
		if ((p->l != NULL)) { write_mid_line(p->l, c); }
		 p->inf =c.front();
		 c.pop();
		 if ((p->r != NULL)) { write_mid_line(p->r, c); }
	}
	
	else
	{



		return;
	}
}
		

void fd(tree* p)
{

	if ((p->l == NULL && p->r == NULL))
	{
		cout << p->inf << " ";
		
	}
	else
	{
		
		if ((p->l != NULL)) { fd(p->l); }
		cout << p->inf << " ";
		if ((p->r != NULL)) { fd(p->r); }
	}
}

int main()
{
	queue<tree*>a;
	queue<int>c;
	int n, m,i,j;
	cin >> n;
	queue<tree*>every_flow_queue;
	
	int* b = new int[n];
	for (i = 0; i < n; i ++)
	{
		cin>>b[i];		
	}
	sort(b, b + n);
	
	for (i = 0; i < n; i++)
	{
	
		c.push(b[i]);
	}
	tree *head=new tree;
	a.push(head);
	head->inf = b[0];


	for (i = 1; i< n; i=i+2) 
	{
		
		if(n-i==1)
		{
			a.front()->creatl();
			a.front()->l->inf = b[i];
			break;
		}
		else
		{
			a.front()->creat();
			a.front()->l->inf = b[i] ;
			a.front()->r->inf = b[i +1];
			a.push(a.front()->l);
			a.push(a.front()->r);
			a.pop();
		}
	}

	
	write_mid_line(head,c);
	

	every_flow_queue.push(head);
	j = 0;
	while (!every_flow_queue.empty())
	{
		if (every_flow_queue.front()->inf != -1) { cout << every_flow_queue.front()->inf; if (j != n - 1) { cout << " "; } }
		if ((every_flow_queue.front()->l != NULL)) { every_flow_queue.push(every_flow_queue.front()->l); }
		if ((every_flow_queue.front()->r != NULL)) { every_flow_queue.push(every_flow_queue.front()->r); }
		every_flow_queue.pop();
		j++;
	}

}


